// #include<vector>
// #include<limits>
// #include<cstddef>
// #include<iostream>
// #include<sstream>
// #include<map>
// #include<algorithm>
// #include<tuple>
// #include<unordered_map>
// #include<functional>
// using namespace std;
// typedef std::tuple<int,int> keyT;
// struct key_hash : public std::unary_function<keyT, std::size_t>{
//     std::size_t operator()(const keyT& k) const {
//         return std::get<0>(k) ^ std::get<1>(k);
//     }
// };
// struct key_equal : public std::binary_function<keyT, keyT, bool>{
//     bool operator()(const keyT& v0, const keyT& v1) const{
//         return std::get<0>(v0) == std::get<0>(v1) && std::get<1>(v0) == std::get<1>(v1);
//     }
// };


// typedef std::unordered_map<const keyT, int, key_hash, key_equal > map_t;
// struct OneF{
//     int price, yanZhi;//y sort 最大
// };
// class Fish{
// public:
//     map_t cache;
//     vector<OneF> fishes;
//     bool reverse = false;
//     int totalC = 0;
//     int MaxP(int startPos, int maxYan){
//         totalC++;
//         if(startPos >= fishes.size()) return 0;
//         auto key = std::make_tuple(startPos, maxYan); 
//         if(cache.find(key) != cache.end()) return cache[key];
//         auto f = fishes[startPos];
//         if(f.yanZhi >= maxYan){
//             auto mv = 0;
//             if(f.yanZhi == maxYan){
//                 auto v1 = MaxP(startPos+1, f.yanZhi)+f.price;
//                 mv = std::max(v1, mv);
//             }else {
//                 auto v1 = MaxP(startPos+1, f.yanZhi)+f.price;
//                 auto v2 = MaxP(startPos+1, maxYan);
//                 mv = std::max(v1, v2);
//             }
//             cache[key] = mv;
//             return mv;
//         }else {
//             auto v = MaxP(startPos+1, maxYan);
//             cache[key] = v;
//             return v;
//         }
//     }

//     int MaxPRev(int startPos, int maxYan){
//         totalC++;
//         // std::cout << startPos<<":" << maxYan << endl;
//         if(startPos < 0) return 0;
//         auto key = std::make_tuple(startPos, maxYan); 
//         if(cache.find(key) != cache.end()) return cache[key];
//         auto f = fishes[startPos];
//         if(f.yanZhi >= maxYan){
//             auto mv = 0;
//             if(f.yanZhi == maxYan){
//                 auto v1 = MaxPRev(startPos-1, f.yanZhi)+f.price;
//                 mv = std::max(v1, mv);
//             }else {
//                 auto v1 = MaxPRev(startPos-1, f.yanZhi)+f.price;
//                 auto v2 = MaxPRev(startPos-1, maxYan);
//                 mv = std::max(v1, v2);
//             }
//             cache[key] = mv;
//             return mv;
//         }else {
//             auto v = MaxPRev(startPos-1, maxYan);
//             cache[key] = v;
//             return v;
//         }
//     }

// };

// int main(int, char**) {
//     // string data("10001 10002 10003 10004 10001");
//     // string data("50001 10001 10002 10003 10004");
//     // string data("-10001 -10002 -10003 -10004 0");
//     // string data("50005 10001 10002 10003 10004");
//     string n;
//     getline(cin, n);
//     auto nn = std::stoi(n);
//     for(auto i = 0; i < nn; i++){
//         string dN;
//         getline(cin, dN);
//         auto dV = std::stoi(dN);
//         string data;
//         getline(cin, data);

//         std::stringstream iss(data);
//         std::vector<int> allTok;
//         std::string token;
//         while(std::getline(iss, token, ' ')){
//             allTok.push_back(std::stoi(token));
//         }
//         vector<OneF> fish;
//         for(auto i = 0; i < allTok.size(); i++){
//             OneF of;
//             of.price = allTok[i]/10000;
//             of.yanZhi = allTok[i]%10000;
//             fish.push_back(of);
//         }
//         Fish ff;
//         ff.fishes = fish;
//         auto r1 = ff.MaxP(0, 0);

//         Fish f2;
//         f2.fishes = fish;
//         f2.reverse = true;
//         auto r2 = f2.MaxPRev(fish.size()-1, 0);
//         // for(auto it = f2.cache.begin(); it != f2.cache.end(); it++){
//         //     auto k = it->first;
//         //     std::cout<< std::get<0>(k) << ":" << std::get<1>(k) << ":" << it->second << endl;
//         // }

//         // std::cout << r1 << ":" << r2 << endl;

//         auto mv = std::max(r1, r2);
//         // std::cout << mv << endl;
//         std::cout <<"Case #" << i+1 << ": " << mv << endl;

//         // std::cout<< ff.totalC << ":" << f2.totalC <<":" << ff.cache.size() << endl;
//     }
    

// }